package lc2;
import java.util.*;
import org.junit.*;

public class Ex1984 {

    class Solution {
        public int minimumDifference(int[] nums, int k) {
            int n = nums.length;
            Arrays.sort(nums);

            int res = Integer.MAX_VALUE;
            int min, max;
    
            for (int t = k - 1; t < n; t++) {
                //移除窗口之外的左边界
                max = nums[t];
                min = nums[t - k + 1];
                res = Math.min(res, max - min);
            }
    
            return res;
        }
    }
    class Solution2 {
        public int minimumDifference(int[] nums, int k) {
            int n = nums.length;
            //min:单调递减栈，最左边是窗口内最小值下标；max：最左为窗口最大值下标。
            Deque<Integer> min = new ArrayDeque<>(), max = new ArrayDeque<>();
            Arrays.sort(nums);

            int res = Integer.MAX_VALUE;
    
            for (int t = 0; t < k - 1; t++) {
                while (!min.isEmpty() && (nums[min.peekLast()] >= nums[t])) {
                    min.pollLast();
                }
                while (!max.isEmpty() && (nums[max.peekLast()] <= nums[t])) {
                    max.pollLast();
                }
                min.offer(t);
                max.offer(t);
            }
    
            for (int t = k - 1; t < n - 1; t++) {
                //移除窗口之外的左边界
                if (!min.isEmpty() && min.peekFirst() == t - k) {
                    min.pollFirst();
                }
                if (!max.isEmpty() && max.peekFirst() == t - k) {
                    max.pollFirst();
                }
                while (!min.isEmpty() && (nums[min.peekLast()] >= nums[t])) {
                    min.pollLast();
                }
                while (!max.isEmpty() && (nums[max.peekLast()] <= nums[t])) {
                    max.pollLast();
                }
                min.offer(t);
                max.offer(t);

                res = Math.min(res, nums[max.peekFirst()] - nums[min.peekFirst()]);
            }
    
            return res;
        }
    }
    class Solution1 {
        public int minimumDifference(int[] nums, int k) {
            int n = nums.length;
            //min:单调递减栈，最左边是窗口内最小值下标；max：最左为窗口最大值下标。
            Deque<Integer> min = new ArrayDeque<>(), max = new ArrayDeque<>();
            int i, j;

            int res = Integer.MAX_VALUE;
    
            for (int t = 0; t < k - 1; t++) {
                while (!min.isEmpty() && (nums[(i = min.peekLast()) % n] >= nums[t])) {
                    min.pollLast();
                }
                while (!max.isEmpty() && (nums[(i = max.peekLast()) % n] <= nums[t])) {
                    max.pollLast();
                }
                min.offer(t);
                max.offer(t);
            }
    
            for (int t = k - 1; t < n + k - 1; t++) {
                j = t % n;
                //移除窗口之外的左边界
                if (!min.isEmpty() && min.peekFirst() == t - k) {
                    min.pollFirst();
                }
                if (!max.isEmpty() && max.peekFirst() == t - k) {
                    max.pollFirst();
                }
                while (!min.isEmpty() && (nums[(i = min.peekLast()) % n] >= nums[j])) {
                    min.pollLast();
                }
                while (!max.isEmpty() && (nums[(i = max.peekLast()) % n] <= nums[j])) {
                    max.pollLast();
                }
                min.offer(t);
                max.offer(t);

                res = Math.min(res, nums[max.peekFirst() % n] - nums[min.peekFirst() % n]);
            }
    
            return res;
        }
    }

    // @Test
    // public void test() {
    //     Solution s = new Solution();
    //     int[] nums = new int[]{9,4,1,7};
    //     System.out.println(s.minimumDifference(nums, 2));
    // }

    @Test
    public void tes2() {
        Solution s = new Solution();
        int[] nums = new int[]{93614,91956,83384,14321,29824,89095,96047,25770,39895};
        System.out.println(s.minimumDifference(nums, 3));
    }
}
